#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    string intToRoman(int num) {
        string res;
        int cnt = num / 1000;
        //M 1000
        for(int i=0; i<cnt; ++i) res += 'M';
        num = num % 1000;

        //D 500
        if(num >= 900) {
            res += "CM";
            num -= 900;
        }
        else {
            if(num / 500){
                res += 'D';
                num -= 500;
            }
        }

        //C 100
        if(num >= 400){
            res += "CD";
            num -= 400;
        }
        else {
            if(num / 100){
                cnt = num / 100;
                for(int i=0; i<cnt; ++i) res += 'C';
                num %= 100;
            }
        }

        //L 50
        if(num >= 90) {
            res += "XC";
            num -= 90;
        }
        else {
            if(num / 50){
                res += 'L';
                num -= 50;
            }
        }

        //X 10
        if(num >= 40){
            res += "XL";
            num -= 40;
        }
        else {
            if(num / 10){
                cnt = num / 10;
                for(int i=0; i<cnt; ++i) res += 'X';
                num %= 10;
            }
        }

        //V 5
        if(num >= 9) {
            res += "IX";
            num -= 9;
        }
        else {
            if(num / 5){
                res += 'V';
                num -= 5;
            }
        }

        //I 1
        if(num >= 4){
            res += "IV";
            num -= 4;
        }
        else {
            if(num / 1){
                cnt = num / 1;
                for(int i=0; i<cnt; ++i) res += 'I';
                num %= 1;
            }
        }

        return res;
    }
};

int main(){
    int num = 37;
}